package com.shangguigu.stack;

/**
 * @author: ZhouBert
 * @date: 2019/10/11
 * @description:	用数组模拟栈
 * 思路分析：
 * 1.定义一个 top 表示栈顶的前一个位置，即初始值-1；
 * 2.入栈的操作，当有数据加入到栈时，top++;stack[top]=data
 * 3.出栈的操作，int value = stack[top];top--;return value
 *
 * 栈的应用场景：见图
 * todo:1.子程序调用
 * todo:2.【处理递归调用】
 * todo:3.【表达式转换-中缀表达式->后缀表达式 与 求值（实际解决）】
 * todo:4.【二叉树遍历】
 * todo:5.【图的深度优先（depth-first）搜索法】
 */
public class MyStackMyVersion implements MyStack {

	/**
	 * 栈顶指针
	 */
	int top;
	/**
	 * 栈最大容量
	 */
	int maxSize;

	/**
	 * 储存元素
	 */
	int[] arr;

	/**
	 * 定义最大容量；初始化栈顶指针；初始化存储空间
	 * @param maxSize
	 */
	public MyStackMyVersion(int maxSize){
		top=-1;
		this.maxSize=maxSize;
		arr=new int[maxSize];
	}

	@Override
	public boolean isFull() {
		return top==(maxSize-1);
	}

	@Override
	public boolean isEmpty() {
		return top==-1;
	}

	@Override
	public void push(int value) {
		if (isFull()){
			return;
		}
		///如果
		else{
			arr[++top]=value;
		}
	}

	@Override
	public int pop() {
		if (isEmpty()){
			return -1;
		}else {
			return arr[top--];
		}

	}

	/**
	 * 此处是从栈尾开始遍历
	 */
	@Override
	public void list() {
		if (isEmpty()){
			return;
		}
		for (int i = 0; i <= top; i++) {
			System.out.printf("%d\t",arr[i]);
		}
	}

	public static void main(String[] args) {
		MyStack stack = new MyStackMyVersion(4);
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);

		stack.list();

		stack.pop();

		stack.list();
	}
}
